#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {  // 双向链表结点结构体
    int data;   // 数据域
    struct DNode *prior;    // 前驱指针
    struct DNode *next;     // 后继指针
} DNode, *DLinkList;        // 双向链表类型定义

// 创建双向链表头结点
DLinkList createDLinkList() {
    DLinkList L = (DLinkList)malloc(sizeof(DNode)); // 分配头结点内存
    L->prior = NULL;    // 头结点前驱指针设为NULL
    L->next = NULL;     // 头结点后继指针设为NULL
    return L;   // 返回头结点指针
}

// 用数组创建双向链表（尾插法）
void createListFromArray(DLinkList L, int arr[], int n) {
    DNode *tail = L; // 尾指针，初始指向头结点
    
    for (int i = 0; i < n; i++) {   // 遍历数组
        DNode *newNode = (DNode *)malloc(sizeof(DNode));    // 创建新节点
        newNode->data = arr[i]; // 赋值数据域
        newNode->prior = tail;  // 新节点前驱指向当前尾节点
        newNode->next = NULL;   // 新节点后继设为NULL
        
        tail->next = newNode;   // 当前尾节点后继指向新节点
        tail = newNode; // 更新尾指针
    }
}

// 反转双向链表
void reverseDLinkList(DLinkList L) {    // L为头结点指针
    if (L->next == NULL || L->next->next == NULL) { 
        return;  // 空链表或只有一个节点，无需反转
    }
    
    DNode *current = L->next;   // 指向第一个节点
    DNode *prior = NULL;    // 用于保存前一个节点
    DNode *next = NULL; // 用于保存下一个节点
    
    // 遍历链表，反转指针方向
    while (current != NULL) {
        next = current->next;      // 保存下一个节点
        current->prior = next;     // 前驱指向原来的后继
        current->next = prior;     // 后继指向原来的前驱
        
        prior = current;           // 更新prior为当前节点
        current = next;            // 移动到下一个节点
    }
    
    // 调整头节点指向新的第一个节点
    L->next = prior;    
    if (prior != NULL) {    // 更新新第一个节点的前驱指向头节点
        prior->prior = L;   // 新第一个节点前驱指向头结点
    }
}

// 显示双向链表内容（正向）
void displayList(DLinkList L) { // 显示链表内容
    DNode *p = L->next; // 指向第一个结点
    printf("链表: 头->");
    while (p != NULL) { // 遍历链表
        printf("%d", p->data);  // 输出数据域
        if (p->next != NULL) {  // 如果不是最后一个节点，输出箭头
            printf("->");   // 输出箭头
        }
        p = p->next;    // 移动到下一个节点
    }
    printf("\n");   // 换行
}

// 显示双向链表内容（带前后指针信息）
void displayListDetailed(DLinkList L) { // 显示链表详细信息
    DNode *p = L->next; // 指向第一个结点
    printf("详细链表信息:\n");  // 显示正向链接
    printf("头节点 -> ");   // 显示正向链接
    
    while (p != NULL) { // 遍历链表
        printf("[%d]", p->data);    // 输出数据域
        if (p->next != NULL) {  // 如果不是最后一个节点，输出箭头
            printf(" -> "); // 输出箭头
        }
        p = p->next;    // 移动到下一个节点
    }
    printf(" -> NULL\n");   // 换行
    
    // 显示反向链接
    printf("NULL <- "); // 显示反向链接
    p = L->next;    // 重新指向第一个结点
    while (p != NULL && p->next != NULL) {  // 移动到最后一个节点
        p = p->next;    // 移动到下一个节点
    }
    
    while (p != L) {    // 反向遍历链表
        printf("[%d]", p->data);    // 输出数据域
        if (p->prior != L) {    // 如果不是头节点，输出箭头
            printf(" <- "); // 输出箭头
        }
        p = p->prior;   // 移动到前一个节点
    }
    printf(" <- 头节点\n"); // 换行
}

int main() {
    // 创建双向链表
    DLinkList L = createDLinkList();
    int arr[] = {1, 2, 3};  // 初始化数组
    int n = sizeof(arr) / sizeof(arr[0]);   // 计算数组长度
    
    // 用数组创建链表
    createListFromArray(L, arr, n);
    
    printf("=== 反转前 ===\n");
    displayList(L); // 显示链表内容
    displayListDetailed(L); // 显示链表详细信息
    
    // 反转链表
    reverseDLinkList(L);
    
    printf("\n=== 反转后 ===\n");
    displayList(L);
    displayListDetailed(L);
    
    return 0;   // 主函数返回
}